#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

//class Solution {
//public:
//    void Adj(vector<int>& nums, int left, int n)
//    {
//        int parent = left;
//        int child = parent * 2 + 1;
//        while (child < n)
//        {
//            if (child + 1 < n && nums[child + 1] > nums[child])
//            {
//                child++;
//            }
//            if (nums[child] > nums[parent])
//            {
//                swap(nums[child], nums[parent]);
//                parent = child;
//                child = parent * 2 + 1;
//            }
//            else
//            {
//                break;
//            }
//        }
//    }
//
//    int findKthLargest(vector<int>& nums, int k)
//    {
//        int n = nums.size();
//        for (int i = (n - 1 - 1) / 2; i >= 0; i--)
//        {
//            Adj(nums, i, n);
//        }
//        int end = n - 1;
//        while (k > 1)
//        {
//            swap(nums[0], nums[end]);
//            Adj(nums, 0, end);
//            end--;
//            k--;
//        }
//        return nums[0];
//    }
//};

class Solution {
public:
    void Adj(vector<int>& nums, int left, int n)
    {
        int parent = left;
        int child = parent * 2 + 1;
        while (child < n)
        {
            if (child + 1 < n && nums[child + 1] < nums[child])
            {
                child++;
            }
            if (nums[child] < nums[parent])
            {
                swap(nums[child], nums[parent]);
                parent = child;
                child = parent * 2 + 1;
            }
            else
            {
                break;
            }
        }
    }
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<vector<int>> ret;
        int n1 = nums1.size();
        for (int i = (n1 - 1 - 1) / 2; i >= 0; i--)
        {
            Adj(nums1, i, n1);
        }
        int end = n1 - 1;
        int n2 = nums1.size();
        sort(nums2.begin(), nums2.end());
        if (k > n1)
        {
            k = n1;
        }
        while (k--)
        {
            int min1 = nums1[0];
            for (int i = 0; i < n2; i++)
            {
                vector<int> p;
                p.push_back(nums1[0]);
                p.push_back(nums2[i]);
                ret.push_back(p);
            }
            swap(nums1[0], nums1[end]);
            Adj(nums1, 0, end);
            end--;
        }
        return ret;
    }
};

int main()
{
    vector<int> nums1 = { 1,7,11 };
    vector<int> nums2 = { 2,4,6 };
    Solution s;
    vector<vector<int>> ret = s.kSmallestPairs(nums1, nums2, 3);
    return 0;
}

//class Solution {
//public:
//    int hammingWeight(uint32_t n) {
//        int num = 0;
//        int i = 0;
//        while (i < 32)
//        {
//            if ((n >> i) & 1 == 1)
//            {
//                num++;
//            }
//            i++;
//        }
//        return num;
//    }
//};
//
//class Solution {
//public:
//    int singleNumber(vector<int>& nums) {
//        int k = nums[0];
//        int n = nums.size();
//        for (int i = 1; i < n; i++)
//        {
//            k = k ^ nums[i];
//        }
//        return k;
//    }
//};

//class Solution {
//public:
//    int rangeBitwiseAnd(int left, int right) {
//        int n = left > right ? left : right;
//        int m = left > right ? right : left;
//        int num = n;
//        for (int i = m; i < n; i++)
//        {
//            num = num & i;
//        }
//        return num;
//    }
//};